(a). Field of the Invention
The present invention relates in general to the field of bandwidth control, and more particularly to an apparatus and method that are able to simplify circuits and to control bandwidth precisely by providing a dual-counter design and simplifying counting operations required by bandwidth control.
(b). Description of the Prior Arts
Due to increasing diversity of Internet applications, there is increasing need for bandwidth. Therefore, it is inevitable for the rising of wideband services. For example, there are more and more Internet service providers (ISP) that provide wideband network services of asymmetrical digital subscriber line (ADSL) and cable modem. However, these two wideband services employ Ethernet connections on client side and the design goal of Ethernet is just providing bandwidth as large as possible, thus if the use of bandwidth of the client side is not controlled, the ISPs won't be able to provide a fare program with various grades for the client side (i.e. charging differently based on different bandwidths), and network equipments of the ISPs may suffer from serious congestion. Besides, for network administrators, it is necessary to control bandwidth to prevent from network congestion in face of fast-growing traffic.
For ISPs and network administrators, a network switch is employed to perform bandwidth control. The switch often utilizes a “leaky bucket” to implement the function of bandwidth control. Please refer to FIG. 1, which is a diagram depicting the operation of a leaky bucket. The leaky bucket 10 is like a funnel that can hold B tokens 11 at most. A packet 13 waiting for transmission must own tokens 11 to pass through a queue 12 onto the network. The tokens 11 decrease with continuous transmission of packets to the network. When the tokens 11 are used up, the transmission is then stopped. Therefore, if the tokens 11 of the bucket 10 are supplied with a constant rate, say R tokens/sec, then data output per unit time can be controlled to achieve the goal of bandwidth control (this is because only a constant quantity of tokens can be used per unit time). The data volume represented by each token varies with different network technologies. For instance, the size of a packet 13 in Ethernet is changeable, thus one byte is taken as the data volume for a token 11; while in Asynchronous Transfer Mode (ATM), a cell of same size is used as transmission unit, so it can be taken as the data volume for the token 11. In addition, when the bucket 10 is full, subsequently supplied tokens will be abandoned.
There are two major implementations for the leaky bucket 10. The first one is to fully implement the leaky bucket 10; the second is a simplified one, which changes the way the leaky bucket 10 supplies tokens 11 from a constant rate to resetting to a full state during every constant time. The advantage of the first one is that it can control bandwidth precisely, but its cost is too high; though the second one can reduce cost significantly, it cannot provide precise bandwidth control.
Next, a detailed description for these two implementations is provided. For the first one, there are two critical variables: stock of the tokens 11 in the bucket 10 and capacity B of the bucket 10. The stock of the tokens 11 is used to determine whether a packet 13 can pass through the queue 12. If the stock of the tokens 11 at time t is represented by CNTR (t), and the tokens 11 are supplied in the rate of R tokens/sec, then the value of CNTR (t) is the smaller of CNTR (t−1)+R and B. When implemented in circuits, a counter is used to record CNTR (t). However, the update of CNTR (t) involves additive operations of larger values, thus the design of related circuits is more complex and costs more.
The second one uses a simple ripple counter for recording the stock of the tokens 11 in the bucket 10 to reduce cost. Though it is easy for the ripple counter to implement an operation of adding or subtracting one, it's hard for it to achieve an operation of adding or subtracting larger values rapidly. Therefore, this implementation replaces the additive operation with a setting one. If the leaky bucket 10 is at first empty and tokens 11 are filled in the rate of R per second, then the bucket 10 will be full after B/R seconds. Hence, in operation, the value of the ripple counter is reset to B every B/R seconds to avoid additive or subtractive operations of larger values required by the first implementation. However, it would result in imprecise bandwidth control. This is because it is uncertain that B tokens 11 be used up during every period of B/R seconds. As long as next period arrives, there are B tokens available again for use, thus the data output per unit time is not constant and precise bandwidth control cannot be achieved.